<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>PlanarGC: Tutorial: CutSegment</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
  $(document).ready(initResizable);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td style="padding-left: 0.5em;">
   <div id="projectname">PlanarGC
   &#160;<span id="projectnumber">1.0.2</span>
   </div>
  </td>
   <td>        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
</td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.1.2 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('a00007.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Data Structures</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Friends</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Pages</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">Tutorial: <a class="el" href="a00015.html">CutSegment</a> </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p><a class="el" href="a00015.html">CutSegment</a> finds a minimal cut in an image where every image pixel represents a graph vertex. We assume a 4-connected grid (cf. <a class="el" href="a00006.html">CutGrid</a>) and that the capacity of an edge only depends on the image information at the two linked pixels.</p>
<div class="image">
<img src="photo.PNG" alt="photo.PNG"/>
<div class="caption">
Example of an image 'I'</div></div>
<div class="image">
<img src="photoSel.PNG" alt="photoSel.PNG"/>
<div class="caption">
Example of a preselected source and sink set 'L'</div></div>
<p>In order to compute the cut, the following steps have to be performed:</p>
<ol type="1">
<li>Define the <a class="el" href="a00007.html#sec_gradientSeg">gradient dependent capacity</a>.</li>
<li>Compute the <a class="el" href="a00007.html#sec_maxflowSeg">maximum flow</a> with respect to a connected source and sink set.</li>
<li><a class="el" href="a00007.html#sec_getcutSeg">Extract the minimal cut</a> as a pixel-based representation.</li>
</ol>
<p>In the following sections, we explain these steps with respect to the graph sketched in the images above.</p>
<h1><a class="anchor" id="sec_gradientSeg"></a>
Gradient Dependent Capacity</h1>
<p>When we define the capacity of each edge, we can either do this by using the GAC approach already implemented or by overwriting the <a class="el" href="a00015.html#aacf6591687eb8d6ecbbc769cec0a711f">CutSegment::gradient(double,double)</a> method. In this example we follow the latter approach:</p>
<div class="fragment"><div class="line"><span class="keyword">class </span>MyCutSegment : <span class="keyword">public</span> <a class="code" href="a00015.html">CutSegment</a> {</div>
<div class="line"><span class="keyword">public</span>:</div>
<div class="line">  MyCutSegment(<span class="keywordtype">int</span> width, <span class="keywordtype">int</span> height) : <a class="code" href="a00015.html">CutSegment</a>(width,height) {};</div>
<div class="line">  <span class="keywordtype">double</span> <a class="code" href="a00015.html#aacf6591687eb8d6ecbbc769cec0a711f">gradient</a>(<span class="keywordtype">double</span> color1, <span class="keywordtype">double</span> color2);</div>
<div class="line">};</div>
<div class="line"></div>
<div class="line"><span class="keywordtype">double</span> <a class="code" href="a00015.html#aacf6591687eb8d6ecbbc769cec0a711f">MyCutSegment::gradient</a>(<span class="keywordtype">double</span> color1, <span class="keywordtype">double</span> color2) {</div>
<div class="line">  <span class="keywordtype">double</span> diff, weight;</div>
<div class="line">  diff   = color1-color2;</div>
<div class="line">  weight = exp(-sqrt(diff*diff));</div>
<div class="line">  <span class="keywordflow">return</span> weight;</div>
<div class="line">}</div>
</div><!-- fragment --><p>If you also want to handle color images correctly, you should also overwrite the <a class="el" href="a00015.html#a2a6f6f03d56eaae0c4ee3e3f66a191ca">CutSegment::gradient(double[3],double[3])</a> method.</p>
<h1><a class="anchor" id="sec_maxflowSeg"></a>
Maximum Flow</h1>
<p>Now, we have to compute the maximum flow. In order to do this via the newly defined MyCutSegment, we have to load the image and the preselected source and sink set into MyCutSegment:</p>
<div class="fragment"><div class="line"><span class="keywordtype">int</span> width=128, height=128;                    <span class="comment">// width and height of the variable I and L</span></div>
<div class="line">MyCutSegment segment_cut(width,height);</div>
<div class="line"></div>
<div class="line">segment_cut.setImageData(I);                  <span class="comment">// load image I</span></div>
<div class="line">segment_cut.setSourceSink(L,0,128);           <span class="comment">// define source and sink via L</span></div>
</div><!-- fragment --><p>We assumed here, that the image is already loaded row-wise in the variable I. In L, a pre-labeling is stored row-wise where the value '0' indicates the pre-selected source set an '128' the pre-selected sink-set. Both areas have to form connected components within L. Otherwise, only one component is considered.</p>
<p>Now that the problem is formulated, we have to compute the value of the maximum flow. This is the most time consuming method of the class and is called via</p>
<div class="fragment"><div class="line"><span class="keywordtype">double</span> flow;</div>
<div class="line"></div>
<div class="line">flow = segment_cut.segment();</div>
</div><!-- fragment --><h1><a class="anchor" id="sec_getcutSeg"></a>
Minimal Cut</h1>
<p>For most applications, we are not only interested in the value of the minimum cut, but also in the segmentation itself. The classical way in describing this is to assign a binary labeling to each pixel. This labeling can be provided via <a class="el" href="a00015.html#ac5f5144a2f5b6355abd1fac7decd7084">CutSegment::getLabel</a> or <a class="el" href="a00015.html#ad6d3c208ed3796f318844e6dc253ad07">CutSegment::getLabels</a></p>
<div class="fragment"><div class="line"><a class="code" href="a00014.html#a0e28d67a0303b0b1a43bb9abbad02989">CutPlanar::ELabel</a>  label;</div>
<div class="line"><a class="code" href="a00014.html#a0e28d67a0303b0b1a43bb9abbad02989">CutPlanar::ELabel</a> *labels;</div>
<div class="line"></div>
<div class="line">label  = segment_cut.getLabel(1,2);                   <span class="comment">// returns &#39;CutPlanar::LABEL_SINK&#39;</span></div>
<div class="line">labels = <span class="keyword">new</span> <a class="code" href="a00014.html#a0e28d67a0303b0b1a43bb9abbad02989">CutPlanar::ELabel</a>[width*height];</div>
<div class="line">segment_cut.getLabels(labels);                </div>
</div><!-- fragment --><p>The complete code can be seen here: <a class="el" href="a00003.html">cutsegment.cpp</a>. </p>
</div></div><!-- contents -->
</div><!-- doc-content -->
<hr class="footer"/><address style="text-align: right;"><small>
  &copy; 2009 - 2013 by Eno T&ouml;ppe, Frank R. Schmidt
  <br/>
  generated by <a href="http://www.doxygen.org/index.html" target="_blank">Doxygen</a>
</small></address>
